#include <stdio.h>
#include <stdlib.h>

// 边的结构体
typedef struct {
    int src, dest, weight;
} Edge;

// 图的结构体
typedef struct {
    int V, E;
    Edge* edge;
} Graph;

// 创建图
Graph* createGraph(int V, int E) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (Edge*) malloc(E * sizeof(Edge));
    return graph;
}

// 并查集的节点
typedef struct {
    int parent;
    int rank;
} Subset;

// 查找函数，带路径压缩
int find(Subset subsets[], int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

// 并集函数，按秩合并
void Union(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

// 用来比较两条边权重的函数
int compareEdges(const void* a, const void* b) {
    Edge* a1 = (Edge*)a;
    Edge* b1 = (Edge*)b;
    return a1->weight > b1->weight;
}

// Kruskal算法主函数
void KruskalMST(Graph* graph) {
    int V = graph->V;
    Edge result[V];  // 用于存储最终的最小生成树
    int e = 0;  // 结果数组的索引
    int i = 0;  // 排序的边数组索引

    // 步骤1: 根据边的权重排序所有的边
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compareEdges);

    // 分配内存给并查集
    Subset* subsets = (Subset*) malloc(V * sizeof(Subset));

    // 初始化并查集
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    // 选取V-1条边
    while (e < V - 1 && i < graph->E) {
        Edge next_edge = graph->edge[i++];

        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);

        // 如果添加这条边不会形成环
        if (x != y) {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
    }

    // 打印构造的MST
    printf("Following are the edges in the constructed MST\n");
    for (i = 0; i < e; ++i)
        printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
    return;
}

int main() {
    int V = 4;  // 顶点数目
    int E = 5;  // 边的数目
    Graph* graph = createGraph(V, E);

    // 添加边：0-1
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 10;

    // 添加边：0-2
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 6;

    // 添加边：0-3
    graph->edge[2].src = 0;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 5;

    // 添加边：1-3
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 15;

    // 添加边：2-3
    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 4;

    KruskalMST(graph);

    return 0;
}
